package com.example;

/**
 * @Author loubobooo
 * @Description #29.两数相除
 * @Date 2022/02/18
 */
public class DivideTwoIntegers {

    /**
     * 方法描述:给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
     * 返回被除数dividend除以除数divisor得到的商。
     * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
     *示例1:
     *
     * 输入: dividend = 10, divisor = 3
     * 输出: 3
     * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
     * @param: [dividend, divisor]
     * @return: int
     * @author: loubobooo
     * @date: 2022/2/18
     */
    public int divide(int dividend, int divisor) {
        // 判断除数和被除数是否为0
        if(dividend == 0 || divisor == 0){
            return 0;
        }
        // 除法结果溢出，则返回 2^31 − 1。
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        // 如果除数和被除数都为正，或者都为负，标记为true
        boolean flag = false;
        if((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)){
            flag = true;
        }
        // 除数和被除数变负数做加减(取反操作)
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
        int result = 0;
        while(dividend <= divisor){
            int temp = divisor;
            int count = 1;
            // 这里注意不要写成 tmp + tmp >= dividend，这样写加法有可能会溢出导致死循环
            while(temp > dividend - temp){
                // tmp 和 count 每次增加一倍，所以叫倍增
                temp += temp;
                count += count;
            }
            // 被除数减去除数的 2^x 倍数做为新的被除数
            dividend -= temp;
            result += count;
        }
        return flag ? result : -result;
    }

}
